/*
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1. 算法步骤
    a.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
    b.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
 */

/*
3.插入排序:

解析：
 （1） 从第一个元素开始，该元素可以认为已经被排序
 （2） 取出下一个元素，在已经排序的元素序列中从后向前扫描
 （3） 如果该元素（已排序）大于新元素(当前正在遍历的元素)，将该元素移到下一位置
 （4） 重复步骤3，直到找到已排序的元素小于或者等于新元素(当前正在遍历的元素)的位置
 （5） 将新元素(当前正在遍历的元素)插入到下一位置中
 （6） 重复步骤2
 */
function insertSort(arr) {
    // 假设index为0的元素是一个有序数列，从index为1以后的都是无序数列
    // 从第2个元素开始遍历，默认第一个元素已经被排序
    for (let i = 1; i < arr.length; i++) {
        // 如果已排序的元素大于当前遍历的元素，将该元素(已排序的元素)移到下一位置
        if (arr[i - 1] > arr[i]) {
            // 存储当前已被排序元素的最后一个元素的下标值，方便后面从后向前扫描已排序的元素
            let sortedLastIndex = i - 1
            let j = sortedLastIndex
            // 使用中间变量存储当前遍历的元素
            let currentTraversalEle = arr[i]
            // 将这个已排序的元素移到下一位置
            arr[i] = arr[j]
            // 重复if的判断条件，直到找到已排序的元素小于或等于当前正在遍历的元素 (j >= 0，是保证边界条件，如：arr[-1]的出现)
            while (j >= 0 && arr[j] > currentTraversalEle) {
                arr[j + 1] = arr[j]
                j--
            }
            // 找到了插入当前遍历元素的位置
            arr[j + 1] = currentTraversalEle
        }
    }

    return arr
}

function insertionSort(arr) {
    // 假设index为0的元素是一个有序数列，从index为1以后的都是无序数列
    // 从第2个元素开始遍历，默认第一个元素已经被排序
    for (let i = 1; i < arr.length; i++) {
        for (let j = i; j > 0; j--) {
            // 如果已被排序的最后一个元素大于外层循环正遍历的元素，将外层循环正遍历的元素与这个已被排序的元素交换位置
            if (arr[j - 1] > arr[j]) {
                let temp = arr[j - 1]
                arr[j - 1] = arr[j]
                arr[j] = temp
            }
        }
    }
    return arr
}

console.log(insertSort([9, 1, 5, 4, 12, 33, 0]))
console.log(insertSort([9, 1, 5, 4, 12, 33, 0, 5]))
console.log(insertSort([9, 1, 5, 4, 12, 33, 0, 12.2, 2.5, 5.3, 4]))

// [ 0, 1, 4, 5, 9, 12, 33 ]
// [ 0, 1, 4, 5, 5, 9, 12, 33 ]
// [ 0, 1, 2.5, 4, 4, 5, 5.3, 9, 12, 12.2, 33 ]

console.log(insertionSort([9, 1, 5, 4, 12, 33, 0]))
console.log(insertionSort([9, 1, 5, 4, 12, 33, 0, 5]))
console.log(insertionSort([9, 1, 5, 4, 12, 33, 0, 12.2, 2.5, 5.3, 4]))

// [ 0, 1, 4, 5, 9, 12, 33 ]
// [ 0, 1, 4, 5, 5, 9, 12, 33 ]
// [ 0, 1, 2.5, 4, 4, 5, 5.3, 9, 12, 12.2, 33 ]
